package com.linyaonan.leetcode.medium._2080;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
 *
 * 子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
 *
 * 请你实现 RangeFreqQuery 类：
 *
 * RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
 * int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
 * 一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：
 * ["RangeFreqQuery", "query", "query"]
 * [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
 * 输出：
 * [null, 1, 2]
 *
 * 解释：
 * RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
 * rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
 * rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。
 *
 *
 * 提示：
 *
 * 1 <= arr.length <= 10^5
 * 1 <= arr[i], value <= 10^4
 * 0 <= left <= right < arr.length
 * 调用 query 不超过 10^5 次。
 *
 * @author: Lin
 * @date: 2024/12/3
 */
public class RangeFreqQuery {

    int[] org;
    HashMap<Integer, List<Integer>> indexMap = new HashMap<>();

    /**
     * 该写法会超时
     * @param arr
     */
    public RangeFreqQuery(int[] arr) {
        org = arr;
        // 把每一个数值对应出现的索引范围按照原始数组顺序记录下来
        for (int i = 0; i < arr.length; i++) {
            int value = arr[i];
            if (indexMap.containsKey(value)) {
                List<Integer> list = indexMap.get(value);
                list.add(i);
                indexMap.put(value, list);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                indexMap.put(value, list);
            }
        }
    }

    public int query(int left, int right, int value) {
        // indexList中的索引是严格按照递增记录的，所以可以使用二分

        // 以left=0，right=11 为例 index 范围在[2,4,5,10]
        List<Integer> indexList = indexMap.get(value);
        int indexL = leftMatch(indexList, left);
        if (indexL == -1) {
            return 0;
        }
        int indexR = rightMatch(indexList, right);
        return indexR - indexL + 1;
    }

    /**
     * target目标值在比目标值数组中大，并且找到最靠左的索引
     * @param indexList
     * @param target
     * @return
     */
    public int leftMatch(List<Integer> indexList, int target) {
        // [3,4] 1
        int l = 0;
        int r = indexList.size() - 1;
        int tt = -1;

        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = indexList.get(m);
            if (temp <= target) {
                tt = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return tt;
    }

    /**
     * target目标值在比目标值数组中小，并且找到最靠右的索引
     * @param indexList
     * @param target
     * @return
     */
    public int rightMatch(List<Integer> indexList, int target) {
        int l = 0;
        int r = indexList.size() - 1;
        int tt = r + 1;

        while (l <= r) {
            int m = (l + r) >>> 1;
            int temp = indexList.get(m);
            if (temp <= target) {
                tt = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return tt;
    }
}
